package com.yangzhe.algorithm.c038;

import java.util.Stack;

// 用递归函数逆序栈
public class Code05_ReverseStackWithRecursive {

    public static void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        } else {
            // 先把底部元素取出来
            int bottom = bottomOut(stack);
            // 逆序剩余堆栈
            reverse(stack);
            // 把底部放在最上面
            stack.push(bottom);
        }
    }

    // 栈底元素移除掉，上面的元素盖下来
    // 返回移除掉的栈底元素
    public static int bottomOut(Stack<Integer> stack) {
        // 先弹出当前递归的数字
        Integer current = stack.pop();
        // 如果弹出后栈空了，代表current就是底部
        if (stack.isEmpty()) {
            return current;
        } else { // 弹出后栈不为空，继续向下寻找
            int bottom = bottomOut(stack);
            // 恢复栈
            stack.push(current);
            return bottom;
        }

    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
		
        reverse(stack);
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }

}
